package 算法.字符串.排序.LSD基数排序;

import util.LogUtils;

/**
 * 【字符串排序：LSD自小而大的基数排序】
 * 		就是：每个字符串：从右向左（从小到大），每个字符使用一次键索引计数法
 *
 * @Date 2017-09-10 
 * @author Administrator
 * @version
 */
public class LSD {
	public void initData(String[] data) {
		
		data[0]  = "4PGC938";
		data[1]  = "2IYE230";
		data[2]  = "3CIO720";
		data[3]  = "1ICK750";
		data[4]  = "1OHV845";
		data[5]  = "4JZY524";
		data[6]  = "1ICK750";
		data[7]  = "3CIO720";
		data[8]  = "1OHV845";
		data[9]  = "1OHV845";
		data[10] = "2RLA629";
		data[11] = "2RLA629";
		data[12] = "3ATW723";
		
	
//		data[0]  = "4PGC938";
//		data[1]  = "2IY";
//		data[2]  = "3CIO720";
//		data[3]  = "1IC";
//		data[4]  = "1OHV845";
//		data[5]  = "4JZY524";
//		data[6]  = "1I";
//		data[7]  = "3CIO720";
//		data[8]  = "1O";
//		data[9]  = "1OHV845";
//		data[10] = "2RLA629";
//		data[11] = "2RLA62";
//		data[12] = "3ATW";
	} 
	
	public void sort(int W) {
		int R = 256;
		String[] data = new String[13];
		
		int N = data.length;
		initData(data);

		//循环每一个字符串
		for (int d = W-1; d >= 0; d--) {
			int[] count = new int[R+1];				//索引0的位置不使用
			String[] aux = new String[N];	//辅助数组
			//计算频数
			for (int i = 0; i < N; i ++) {
				char ch = data[i].charAt(d);
				count[ch+1]++;					  
			}
			//计算字符串索引开始的位置
			for (int i = 0; i < R; i ++) {	//因为要遍历count，所以i<R(count的长度为R+1)
				count[i+1] += count[i];
			}
			//赋值到辅助数组中
			for (int i = 0; i < N; i ++) {
				String ele = data[i];
				aux[count[ele.charAt(d)]++] = ele;
			}
			//返回数据
			for (int i = 0; i < N; i ++) {
				data[i] = aux[i];
			}
			//输出结果
			traverse(d, data);
		}
		//输出结果
		traverse(0, data);
	}
	
	private void traverse(int d, String[] data) {
		for (int i = 0; i < data.length; i ++) {
			LogUtils.println("LSD>>"+d, data[i]);
		}
		LogUtils.println(">>>>>>>>>>>>>>>>", ">>>>>>>>>>>>>>>>>>>>>>>>>");
	}
	
	public static void main(String[] args) {
		LSD lsd = new LSD();
		lsd.sort(7);		//每个元素的长度为7(共7个字符 )
	}
}
